package leetcode.hot100;

public class Solution300 {

    public static void main(String[] args) {
        int[] ints = {10,9,2,5,3,7,101,18};
        System.out.println(lengthOfLIS(ints));
    }

    public static int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        int maxLen = 0;
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
            //对前面所有确定长度的位置进行遍历
            // TODO: 2021/6/7 这个循环应该可以优化 
            for (int j = 0; j < i; j++) {
                if(nums[j]>=nums[i]) continue;
                dp[i] = Math.max(dp[i],dp[j]+1);
            }
            //更新全局最大
            maxLen = Math.max(dp[i],maxLen);
        }
        return maxLen;
    }
}
